/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Huffman;

import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;

/** This class implements a binary tree suitable for use in Huffman coding.
  * @author Michael Barnathan
*/
public class HuffmanTree implements Comparable<HuffmanTree> {
	/** The value stored in this tree node. */
	public Character value;

	/** The left child of the tree. */
	public HuffmanTree left;

	/** The right child of the tree. */
	public HuffmanTree right;

	/** The codeword frequency of the value. */
	public double frequency;

	/** Creates a new Huffman tree with the specified value, frequency, and children. */
	public HuffmanTree(Character value, double freq, HuffmanTree left, HuffmanTree right) {
		this.value = value;
		this.frequency = freq;
		this.left = left;
		this.right = right;
	}

	/** Creates a leaf node with the specified value and frequency. */
	public HuffmanTree(Character value, double freq) { this(value, freq, null, null); }

	/** Creates a null-valued 0-frequency leaf node. */
	public HuffmanTree() { this(null, 0.0); }


	/** Builds a HuffmanTree from a FrequencyTable.
	  * @param freqs a table containing character frequencies.
	  * @return a Huffman tree containing the characters' prefix codes. */
	public static HuffmanTree buildTree(FrequencyTable freqs) {
		//The Huffman algorithm operates by growing a tree from the
		//two lowest frequencies specified in the table.
		//These naturally form a heap, implemented as a priority queue.

		PriorityQueue<HuffmanTree> huffq = new PriorityQueue<HuffmanTree>();

		//First, add the leaves of the tree directly from the frequency table.
		for (Map.Entry<Character, Double> mapping : freqs.entrySet())
			huffq.add(new HuffmanTree(mapping.getKey(), mapping.getValue()));

		//Next, iteratively build the tree by merging queue nodes until only 1 remains.
		while (huffq.size() > 1) {
			HuffmanTree newnode = new HuffmanTree();
			newnode.left = huffq.remove();
			newnode.right = huffq.remove();

			//The frequencies are added. The value remains null.
			newnode.frequency = newnode.left.frequency + newnode.right.frequency;

			//Re-enqueue the merged node (2 nodes to 1; the queue size shrinks).
			huffq.add(newnode);
		}

		//The node remaining in the queue becomes the root of the Huffman tree.
		return huffq.remove();
	}


	/** This function traverses the tree and returns all
	  * of the Huffman codes contained within it.
	  * @return a HashMap containing mappings between characters and codes, in ASCII. */
	public final HashMap<Character, String> getCodes() {
		//No use traversing an empty tree!
		if (left == null && right == null)
			return null;

		HashMap<Character, String> ret = new HashMap<Character, String>();

		//Traverse the tree and populate the HashMap each time we reach a leaf.
		traverse("", ret);
		return ret;
	}


	/** A recursive tree traversal call. Builds Huffman codes when leaves are traversed. */
	private void traverse(String currentcode, HashMap<Character, String> curmappings) {
		//Associate each leaf's value with its Huffman code.
		if (left == null && right == null)
			curmappings.put(value, currentcode);
		
		if (left != null)
			left.traverse(currentcode + "0", curmappings);

		if (right != null)
			right.traverse(currentcode + "1", curmappings);
	}

	/** Compares by frequency. */
	public int compareTo(HuffmanTree rhs) {
		return (frequency < rhs.frequency) ? -1 : ((frequency > rhs.frequency) ? 1 : 0);
	}
}